/*
Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
*/
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct ListNode
{
    int val;
    ListNode * next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode * removeNthFromEnd(ListNode * head, int n)
{
    ListNode * tmp = head;
    int length = 0;
    while (nullptr != tmp) {
        tmp = tmp->next;
        ++length;
    } 
    
    int pos = length - n;
    ListNode * curr = head, * pre = head;
    while (pos > 0) {
        pre = curr;
        if (nullptr == curr->next) {
            curr = head;
        } else {
            curr = curr->next;
        }
        --pos;
    }
    if (curr == head) {
        head = head->next;
        pre = nullptr;
    } else {
        pre->next = curr->next;
    }
    delete curr;
    curr = nullptr;
    return head;
}


int main(int argc, const char * argv[])
{
    ListNode * head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    removeNthFromEnd(head, 1);
    return 0;
}
